package com.chj.gaoji.class14;

import java.util.ArrayList;
import java.util.List;

// https://leetcode-cn.com/problems/palindrome-pairs/solution/javazi-dian-shu-by-shiningshar/
public class Code10_PalindromePairs {
	public static class Trie {
		Trie[] next;
		// end表示这目前这棵树是那一个索引单词的结尾
		int end;

		public Trie() {
			this.next = new Trie[26];
			this.end = -1;
		}

		// 由于待会儿用到字典树的时候，是找目标串的翻转字符串，所以插入的时候，应该是倒序插入
		public void insert(String s, int endNum) {
			char[] chars = s.toCharArray();
			Trie cur = this;
			for (int i = 0; i < chars.length; i++) {
				int index = chars[i] - 'a';
				if (cur.next[index] == null)
					cur.next[index] = new Trie();
				cur = cur.next[index];
			}
			cur.end = endNum;
		}
	}

	public static List<List<Integer>> palindromePairs(String[] words) {
		// 构建字典树
		Trie trie = new Trie();
		for (int i = 0; i < words.length; i++) {
			trie.insert(reverse(words[i]), i);
		}
		List<List<Integer>> res = new ArrayList<>();
		for (int i = 0; i < words.length; i++) {
			String word = words[i];
			int wordLen = word.length();
			int[] rss = manacherss(word);

			// 先去字典树中找整个单词的翻转作为特殊情况考虑
			int index = findWord(trie, word);
			if (index != -1 && index != i) {
				addRes(res, i, index);
			}
			// 还有一种特殊情况，我也是提交了没有通过才发现的，就是单词里有空字符串"",
			// 这意味他可以放在任何回文串的首尾
			int wMid = (wordLen - 1) / 2;
			int mid = wordLen % 2 == 0 ? (wMid + 1) * 2 : (wMid + 1) * 2 - 1;
			if (wordLen != 0 && mid - rss[mid] == -1) {
				index = findWord(trie, "");
				if (index != -1 && index != i) {
					addRes(res, i, index);
					addRes(res, index, i);
				}
			}

			for (int j = 0; j < word.length(); j++) {

				String ls = word.substring(0, j + 1);
				String rs = word.substring(j + 1);
				// 先判断前半部分[0, j]是不是回文串
				mid = j % 2 == 0 ? (j / 2 + 1) * 2 - 1 : (j / 2 + 1) * 2;
				if (mid - rss[mid] == -1 && rs.length() != 0) {
					int pre = findWord(trie, rs);
					if (pre != -1 && pre != i)
						addRes(res, pre, i);
				}

				int eLen = wordLen - (j + 1);
				int eMid = j + 1 + (wordLen - 1 - (j + 1)) / 2;

				mid = eLen % 2 == 0 ? (eMid + 1) * 2 : (eMid + 1) * 2 - 1;
				// 再判断[j + 1, end],一定要加j != word.length() - 1,要不然会和上面找整个字符串的翻转重复
				if (j != word.length() - 1 && mid + rss[mid] == rss.length) {
					int after = findWord(trie, ls);
					if (after != -1 && after != i)
						addRes(res, i, after);
				}
			}
		}
		return res;
	}

	private static void addRes(List<List<Integer>> res, int i, int j) {
		List<Integer> list = new ArrayList<>();
		list.add(i);
		list.add(j);
		res.add(list);
	}

	private static int findWord(Trie trie, String word) {
		Trie cur = trie;
		char[] chars = word.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			int temp = chars[i] - 'a';
			if (cur.next[temp] == null)
				return -1;
			else
				cur = cur.next[temp];
		}
		return cur.end;
	}

	private static String reverse(String str) {
		char[] chs = str.toCharArray();
		int l = 0;
		int r = chs.length - 1;
		while (l < r) {
			char tmp = chs[l];
			chs[l++] = chs[r];
			chs[r--] = tmp;
		}
		return String.valueOf(chs);
	}

	public static int[] manacherss(String word) {
		char[] mchs = manachercs(word);
		int[] rs = new int[mchs.length];
		int center = -1;
		int pr = -1;
		for (int i = 0; i != mchs.length; i++) {
			rs[i] = pr > i ? Math.min(rs[(center << 1) - i], pr - i) : 1;
			while (i + rs[i] < mchs.length && i - rs[i] > -1) {
				if (mchs[i + rs[i]] != mchs[i - rs[i]]) {
					break;
				}
				rs[i]++;
			}
			if (i + rs[i] > pr) {
				pr = i + rs[i];
				center = i;
			}
		}
		return rs;
	}

	public static char[] manachercs(String word) {
		char[] chs = word.toCharArray();
		char[] mchs = new char[chs.length * 2 + 1];
		int index = 0;
		for (int i = 0; i != mchs.length; i++) {
			mchs[i] = (i & 1) == 0 ? '#' : chs[index++];
		}
		return mchs;
	}

//	private boolean isPalindrome(String s) {
//		int i = 0;
//		int j = s.length() - 1;
//		char[] letters = s.toCharArray();
//		while (i < j) {
//			if (letters[i] != letters[j])
//				return false;
//			i++;
//			j--;
//		}
//		return true;
//	}

//	private String reverse(String word) {
//		StringBuilder sb = new StringBuilder(word);
//		return sb.reverse().toString();
//	}

//	作者：ShiningShar
//	链接：https://leetcode-cn.com/problems/palindrome-pairs/solution/javazi-dian-shu-by-shiningshar/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static void main(String[] args) {
//		{
//			String test = "112321";
//			System.out.println(String.valueOf(manachercs(test)));
//			int[] arr = manacherss(test);
//			for (int i = 0; i < arr.length; i++) {
//				System.out.print(arr[i] + " ");
//			}
//			System.out.println();
//		}

		{
//			输入：["abcd","dcba","lls","s","sssll"]
//		         输出：[[0,1],[1,0],[3,2],[2,4]] 
//			解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
//
//			来源：力扣（LeetCode）
//			链接：https://leetcode-cn.com/problems/palindrome-pairs
//			著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//			String[] words = new String[] { "", "abcd", "dcba", "lls", "s", "sssll", "" };
//			List<List<Integer>> res = palindromePairs(words);
//			System.out.println(res);
//			System.out.println("dcba".substring(0));
//			System.out.println("dcba".substring(1));
		}

		{
//			输入：["abcd","dcba","lls","s","sssll"]
//		         输出：[[0,1],[1,0],[3,2],[2,4]] 
//			解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
//
//			来源：力扣（LeetCode）
//			链接：https://leetcode-cn.com/problems/palindrome-pairs
//			著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
			String[] words = new String[] { "bb", "" };
			List<List<Integer>> res = palindromePairs(words);
			System.out.println(res);
//			[[0,3],[3,0],[2,3],[3,2]]
//			[[3,0],[1,3],[4,0],[2,4],[5,0],[0,5]]

//			[[1, 3], [2, 4], [0, 5]]
		}

	}
}
